2018“百度之星”程序设计大赛 - 复赛

比赛

比赛链接

A. 没有兄弟的舞会

一看这题目就让我想到‘cv-没有上司的舞会’。。。

看完题目第一反应是树形DP吗？

好像是贪心。。。先不考虑兄弟节点，最小值是所有点的子节点中最小的 vi 的和，最大值是所有点的子节点中最大的 vi 的和。然后枚举兄弟节点，计算并输出。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const ll inf = 1e18;
ll T, n, a[100005], fa[100005], maxn, minn;
ll Max[100005][2], Min[100005][2];

vector<ll> nxt[100005];

int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        for (int i = 2; i <= n; i++) {
            scanf("%lld", &fa[i]);
        }
        for (int i = 1; i <= n; i++) nxt[i].clear();
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            nxt[fa[i]].push_back(a[i]);
        }
        for (int i = 1; i <= n; i++)
            sort(nxt[i].begin(), nxt[i].end());
        int pos1 = 0, pos2 = 0;
        maxn = -inf, minn = inf;
        for (int i = 1; i <= n; i++) {
            int size = (int)nxt[i].size();
            if (size >= 2) {
                if (maxn < nxt[i][size - 2])
                    maxn = nxt[i][size - 2], pos1 = i;
                if (minn > nxt[i][1])
                    minn = nxt[i][1], pos2 = i;
            }
        }
        ll ans1 = 0, ans2 = 0;
        for (int i = 1; i <= n; i++) {
            int size = (int)nxt[i].size();
            if (size > 0) {
                ans1 = max(ans1, ans1 + nxt[i][size - 1]);
                ans2 = min(ans2, ans2 + nxt[i][0]);
            }
        }
        if (pos1) {
            ans1 = max(ans1, ans1 + maxn);
        }
        if (pos2) {
            ans2 = min(ans2, ans2 + minn);
        }
        ans1 = max(ans1, ans1 + a[1]);
        ans2 = min(ans2, ans2 + a[1]);
        printf("%lld %lld\n", ans1, ans2);
    }
    return 0;
}

B. 序列期望

$(\prod_{l_i \le h \le r_i} \sum_{x_i = l_i}^{h} h - x_i) (\prod_{r_i < h} \sum_{x_i = l_i}^{r_i} h - x_i)$